2022 Computer Algorithm                 < No.4 우주 정거장>                Prof. Zoh Q.

우주 정거장

[문제]   튜브(Tube) 모양의 우주 정거장 [eqn: S_1 = (`A`,`B``)]와 [eqn: S _{2} =(`C`,`D``)]가 있다. [eqn: S _{1}]은 우주 3차원 공간의 두 점 A, B를 튜브로 연결하고 있으며 [eqn: S _{2}]는 C점과 D점을 연결하고 있다. 우리는 이 두 튜브 모양의 우주 정거장을 연결하는 연결 통로(bridge link) [eqn: T]를 건설하려고 한다. 단, 우주에서의 공사작업은 매우 큰 비용이 들기 때문에 둘을 연결하는 가장 짧은 길이의 연결 통로를 찾아야 한다. 즉, [eqn: T]는 [eqn: S _{1}]과 [eqn: S _{2}]를 연결하는 최소 정수 길이의 선분이 되어야 한다. 경우에 따라서는 정거장의 끝점이 통로의 연결 시작점이 될 수도 있다.

연결 통로를 만드는데 필요한 부품은 단위 길이로 제공되므로 반드시 그 길이는 정수가 되어야 한다.

그림-1.  두개의 튜브형 우주 정거장 (A,B)와 (C,D)를 연결하는 최단 통로 선분 ([eqn: p,q])

[입출력]  입력 파일 stdin 의 첫 4개의 줄에 두 우주 정거장의 양 끝점 [eqn: A,`B,`C,`D]의 각 3차원 좌표 [eqn: (x,y,z)]가  3개 정수로 주어진다. 각 좌표의 범위는 [eqn: -10,000` LEQ x,``y`,`z LEQ 10,000]이다. 여러분은 두 정거장을 연결하는 통로의 최소 정수 길이를 계산하여 stdout에 출력해야 한다. 예를 들어 연결 통로 [eqn: T]의 길이가 14.0923 라면 15,  156.0이라면 156으로 출력해야 한다.

[제한조건] 프로그램 이름은 station.{c,cpp,java,py}이며 제출 허용 횟수는 15회이다. 데이터 당 제한시간은 최대 1초.

[예제]

stdin	stdout
350 150 350 // A 좌표 0 0 0 // B 좌표 10 –6 30 // C 좌표 56 21 120 // D 좌표	20
700 -940 -854 -390 619 340 3 907 -17 111 222 333	305
0 0 0 0 10000 10000 0 5000 5000 5000 5000 5000	0

[연습용 데이터] 서로 다른 3방향에서 관측했을 때의 모양이 그림-2, 3, 4에 제공되어 있습니다. 그림-4는 두 선분이 맞닿아 있는 경우를 나타내고 있습니다.

stdin	stdout
350 150 350 // A 좌표 0 0 0 // B 좌표 10 –6 30 // C 좌표 56 21 120 // D 좌표	20 //그림-2
700 -940 -854 -390 619 340 3 907 -17 111 222 333	305 //그림-3
0 0 0 0 10000 10000 0 5000 5000 5000 5000 5000	0 //그림-4

그림-2 샘플 데이터 1번의 3차원 공간 그래프

그림-3 샘플 데이터 2번의 3차원 공간 그래프

그림-4 샘플 데이터 3번의 3차원 공간 그래프